백준 5719번

오늘 풀어본 문제는 백준의 5719번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다.

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자. 원은 장소를 의미하고, 선은 단방향 도로를 나타낸다. 시작점은 $S$, 도착점은 $D$ 로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)거의 최단 경로는 점선으로 표시된 경로이다. 이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다. 거의 최단 경로는 여러 개 존재할 수도 있다. 예를 들어, 아래 그림의 길이가 $3$ 인 도로의 길이가 $1$ 이라면, 거의 최단 경로는 두 개가 된다. 또, 거의 최단 경로가 없는 경우도 있다.

map of road

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 $N$ $(2 \le N \le 500)과 도로의 수 M (1 \le M \le 10^4)가 주어진다. 장소는 $0$ 부터 $N-1$ 번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 $S$ 와 도착점 $D$ 가 주어진다. $(S \neq D ; 0 \le S, D < N)$ 다음 $M$ 개 줄에는 도로의 정보 $U$, $V$, $P$ 가 주어진다. $(U \neq V ; 0 \le U, V < N; 1 \le P \le 10^3)$ 이 뜻은 $U$ 에서 $V$ 로 가는 도로의 길이가 $P$ 라는 뜻이다. $U$ 에서 $V$ 로 가는 도로는 최대 한 개이다. 또, $U$ 에서 $V$ 로 가는 도로와 $V$ 에서 $U$ 로 가는 도로는 다른 도로이다.

입력의 마지막 줄에는 $0$ 이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다. 만약, 거의 최단 경로가 없는 경우에는 $-1$ 을 출력한다.

풀이과정

1번째 시도

문제를 해결하기 위해 사용한 방식은 다음과 같다.

그래프의 정보를 입력받고, 다익스트라 알고리즘을 이용하여 최단 경로의 길이를 알아낸다.
시작점에서부터 깊이 우선 탐색을 통해 도착점까지의 거리가 최단 경로와 일치하는 간선들을 제거한다.
간선들이 제거된 그래프에서 다시 한 번 다익스트라 알고리즘을 사용하여 ‘거의 최단경로’의 길이를 알아낸다.

코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.

custom_algorithms.hpp (일부분)

namespace dijkstra {
    template <template<typename, typename> typename Table, typename Node, typename Distance>
    Table<Node, Distance> getShortestPath(Table<Node, Table<Node, Distance>>& graph, const Node& start) {
        Table<Node, Distance> distance;
        distance[start] = 0;

        struct cmp {
            bool operator()(const std::pair<Node, Distance>& a, const std::pair<Node, Distance>& b) {
                return a.second > b.second;
            }
        };

        std::priority_queue<std::pair<Node, Distance>, std::vector<std::pair<Node, Distance>>, cmp> pq;
        pq.push(std::make_pair(start, 0));

        while (!pq.empty()) {
            auto [currNode, currDist] = pq.top();
            pq.pop();

            if (distance.find(currNode) != distance.end() && distance[currNode] < currDist) {
                continue;
            }

            for (auto [next, weight] : graph[currNode]) {
                if (weight < 0) {
                    distance.clear();
                    return distance;
                }
                if (distance.find(next) == distance.end() || distance[next] > currDist + weight) {
                    distance[next] = currDist + weight;
                    pq.push(std::make_pair(next, distance[next]));
                }
            }
        }

        return distance;
    }
}

main.cpp

#include <bits/extc++.h>
#include "custom_algorithms.hpp"

using namespace __gnu_pbds;
using namespace std;

using namespace custom_algorithms;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

bool solve(void);
bool RemoveShortestPaths(gp_hash_table<ll, gp_hash_table<ll, ll>>& table, ll curr, ll dest, ll depth);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (solve());
	
	return 0;
}

bool solve(void) {
	ll N, M;
	cin >> N >> M;

	if (N == 0 && M == 0) {
		return false;
	}

	ll S, D;
	cin >> S >> D;
	
	gp_hash_table<ll, gp_hash_table<ll, ll>> table;
	
	while (M--) {
		ll U, V, P;
		cin >> U >> V >> P;
		
		table[U][V] = P;
	}
	
	auto result = shortest_path::dijkstra::getShortestPath(table, S);
	RemoveShortestPaths(table, S, D, result[D]);
	
	result = shortest_path::dijkstra::getShortestPath(table, S);
	
	if (result.find(D) == result.end()) {
		cout << -1 << '\n';
	}
	else {
		cout << result[D] << '\n';
	}	
	
	return true;
}

bool RemoveShortestPaths(gp_hash_table<ll, gp_hash_table<ll, ll>>& table, ll curr, ll dest, ll depth) {
	vector<ll> nodes_to_disconnect;
	
	for (auto& [next, length] : table[curr]) {
		if (length == depth && next == dest) {
			nodes_to_disconnect.emplace_back(next);
		}
		else if (depth > length) {
			bool search_result = RemoveShortestPaths(table, next, dest, depth - length);
			
			if (search_result == true) {
				nodes_to_disconnect.emplace_back(next);
			}
		}
	}
	
	if (nodes_to_disconnect.empty()) {
		return false;
	}
	else {
		for (auto& next : nodes_to_disconnect) {
			table[curr].erase(next);
		}
		return true;
	}
}

실행 결과 ‘시간 초과’ 가 떴다.

2, 3번째 시도

‘시간 초과’의 발생 원인으로 우선 생각한 것은 중복된 방문이었고, 이를 해결해주기 위해 어떤 노드를 이미 방문하였는지 저장하는 visited 변수를 추가해주었다.

코드를 처음 수정할 때 RemoveShortestPaths 함수의 인자 입력 방식이 바뀌었는데 함수를 사용할 때 이를 제대로 반영하지 않아 2번째 실행 결과로 ‘컴파일 에러’를 받았고, 3번째 시도에서는 이를 제대로 수정하였다.

코드는 main.cpp 파일만 다음과 같이 수정하였다.

main.cpp

#include <bits/extc++.h>
#include "custom_algorithms.hpp"

using namespace __gnu_pbds;
using namespace std;

using namespace custom_algorithms;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

bool solve(void);
bool RemoveShortestPaths(gp_hash_table<ll, gp_hash_table<ll, ll>>& table, vector<bool>& visited, ll curr, ll dest, ll depth);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (solve());
	
	return 0;
}

bool solve(void) {
	ll N, M;
	cin >> N >> M;

	if (N == 0 && M == 0) {
		return false;
	}

	ll S, D;
	cin >> S >> D;
	
	gp_hash_table<ll, gp_hash_table<ll, ll>> table;
	
	while (M--) {
		ll U, V, P;
		cin >> U >> V >> P;
		
		table[U][V] = P;
	}
	
	auto result = shortest_path::dijkstra::getShortestPath(table, S);
	vector<bool> visited(N, false);
	
	RemoveShortestPaths(table, visited, S, D, result[D]);
	
	result = shortest_path::dijkstra::getShortestPath(table, S);
	
	if (result.find(D) == result.end()) {
		cout << -1 << '\n';
	}
	else {
		cout << result[D] << '\n';
	}	
	
	return true;
}

bool RemoveShortestPaths(gp_hash_table<ll, gp_hash_table<ll, ll>>& table, vector<bool>& visited, ll curr, ll dest, ll depth) {
	vector<ll> nodes_to_disconnect;
	
	for (auto& [next, length] : table[curr]) {
		if (visited[next] == true) {
			continue;
		}
		
		if (length == depth && next == dest) {
			visited[curr] = true;
			nodes_to_disconnect.emplace_back(next);
		}
		else if (depth > length) {
			bool search_result = RemoveShortestPaths(table, visited, next, dest, depth - length);
			
			if (search_result == true) {
				visited[curr] = true;
				nodes_to_disconnect.emplace_back(next);
			}
		}
	}
	
	if (nodes_to_disconnect.empty()) {
		return false;
	}
	else {
		for (auto& next : nodes_to_disconnect) {
			table[curr].erase(next);
		}
		return true;
	}
}

실행 결과 ‘틀렸습니다’ 가 떴다.

4번째 시도

질문 게시판에 올라온 여러 가지 테스트 케이스들을 테스트 해본 결과, 간선을 마지막에 제거하는 것이 아닌 탐색 과정중에 제거하기 때문에 일부 간선이 제대로 제거되지 않는 경우가 있었다.

이에 새롭게 이용하기로한 해결 방식은 도착점에서 역으로 추적을 해나가는 것이었다. 내가 만든 다익스트라 알고리즘은 시작점에서 다른 모든 정점까지의 최단 경로의 길이를 저장한 테이블을 반환하기 때문에 갈 필요없는 정점에 대해서는 탐색하지 않을 것이고, 역방향 그래프에서 탐색을 진행하기 때문에 원래 그래프를 즉각적으로 수정해도 놓치게 되는 간선이 없을 것이라고 생각했다.

코드는 main.cpp 파일만 다음과 같이 수정하였다.

main.cpp

#include <bits/extc++.h>
#include "custom_algorithms.hpp"

using namespace __gnu_pbds;
using namespace std;

using namespace custom_algorithms;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

using Graph = gp_hash_table<ll, gp_hash_table<ll, ll>>;

bool solve(void);
void RemoveShortestPaths(Graph& graph, Graph& reversed_graph, gp_hash_table<ll, ll>& dist, ll curr, vector<bool>& visited);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (solve());
	
	return 0;
}

bool solve(void) {
	ll N, M;
	cin >> N >> M;

	if (N == 0 && M == 0) {
		return false;
	}

	ll S, D;
	cin >> S >> D;
	
	Graph graph, reversed_graph;
	
	while (M--) {
		ll U, V, P;
		cin >> U >> V >> P;
		
		graph[U][V] = P;
		reversed_graph[V][U] = P;
	}
	
	auto result = shortest_path::dijkstra::getShortestPath(graph, S);
	vector<bool> visited(N, false);
		
	RemoveShortestPaths(graph, reversed_graph, result, D, visited);
	
	result = shortest_path::dijkstra::getShortestPath(graph, S);
	
	if (result.find(D) == result.end()) {
		cout << -1 << '\n';
	}
	else {
		cout << result[D] << '\n';
	}	
	
	return true;
}

void RemoveShortestPaths(Graph& graph, Graph& reversed_graph, gp_hash_table<ll, ll>& dist, ll curr, vector<bool>& visited) {
    if (visited[curr]) return;
    visited[curr] = true;
    for (auto& [prev, weight] : reversed_graph[curr]) {
        if (dist.find(prev) != dist.end() && dist[prev] + weight == dist[curr]) {
            graph[prev].erase(curr);
            RemoveShortestPaths(graph, reversed_graph, dist, prev, visited);
        }
    }
}

실행 결과 ‘틀렸습니다’ 가 떴다.

5번째 시도

알고리즘에는 분명 문제가 없다고 생각해서 내부 동작을 뜯어봤는데, 어떤 간선들을 확인하지 않는다는 것을 알 수 있었다. 혹시나 해서 __gnu_pbds::gp_hash_table 대신 std::vector 를 이용하여 그래프를 다루도록 해보았다.

코드는 main.cpp 파일만 다음과 같이 수정하였다.

#include <bits/extc++.h>
#include "custom_algorithms.hpp"

using namespace __gnu_pbds;
using namespace std;

using namespace custom_algorithms;

using ll = long long int;
using ull = unsigned long long int;

using ld = long double;
using pll = pair<ll, ll>;

using Graph = vector<vector<pll>>;

bool solve(void);
void RemoveShortestPaths(Graph& graph, const Graph& reversed_graph, const vector<ll>& dist, ll curr, vector<bool>& visited);

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	while (solve());
	
	return 0;
}

bool solve(void) {
	ll N, M;
	cin >> N >> M;

	if (N == 0 && M == 0) {
		return false;
	}

	ll S, D;
	cin >> S >> D;
	
	Graph graph(N), reversed_graph(N);
	
	while (M--) {
		ll U, V, P;
		cin >> U >> V >> P;
		
		graph[U].emplace_back(make_pair(V, P));
		reversed_graph[V].emplace_back(make_pair(U, P));
	}
	
	auto result = shortest_path::dijkstra::GetShortestPath(graph, S);
	vector<bool> visited(N, false);
		
	RemoveShortestPaths(graph, reversed_graph, result, D, visited);
	
	result = shortest_path::dijkstra::GetShortestPath(graph, S);
	
	cout << result[D] << '\n';
	
	return true;
}

void RemoveShortestPaths(Graph& graph, const Graph& reversed_graph, const vector<ll>& dist, ll curr, vector<bool>& visited) {
	if (visited[curr]) return;
    visited[curr] = true;
	
    for (auto [prev, weight] : reversed_graph[curr]) {
		if (dist[prev] != -1 && dist[prev] + weight == dist[curr]) {
			graph[prev].erase(remove(graph[prev].begin(), graph[prev].end(), make_pair(curr, weight)), graph[prev].end());
			RemoveShortestPaths(graph, reversed_graph, dist, prev, visited);
		}
    }
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

일단 풀긴 풀었는데 뭔가 기분이 찜찜하다. 내 생각대로라면 __gnu_pbds::gp_hash_table 을 쓰나 std::vector 를 쓰나 결과에는 차이가 없어야 하는데, 어째서 한쪽은 제대로 작동하지 않고 나머지 한쪽만 제대로 작동하는지 모르겠다…

지금은 이 문제를 푸는데만 해도 상당한 시간과 정신력을 소모했기 때문에 지금은 이 문제를 더 깊이 파고들지 않으려고 한다. 앞으로 비슷한 상황이 나오면 그 때 좀 더 자세히 알아봐야겠다.

내가 작성한 custom_algorithms.hpp 파일은 내 깃헙 레포지토리²에서 확인할 수 있다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/5719
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/5719/custom_algorithms.hpp

← Previous Post END